Graph Theory
Q1.
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?Q2.
Consider the following directed graph: Which of the following is/are correct about the graph?[MSQ]Q3.
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1. The sum of the quality-scores of all vertices on the graph shown above is ______Q4.
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.Q6.
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G) denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\} Which of the following statements is/are TRUE?Q7.
Let G be an undirected complete graph on n vertices, where n\gt2. Then, the number of different Hamiltonian cycles in G is equal toQ8.
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .Q9.
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______Q10.
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of